{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum of Distinct Subarrays With Length K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSubarraySum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #长度为 K 子数组中的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> 。请你从 <code>nums</code> 中满足下述条件的全部子数组中找出最大子数组和：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子数组的长度是 <code>k</code>，且</li>\n",
    "\t<li>子数组中的所有元素 <strong>各不相同 。</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中一段连续非空的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,5,4,2,9,9,9], k = 3\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>nums 中长度为 3 的子数组是：\n",
    "- [1,5,4] 满足全部条件，和为 10 。\n",
    "- [5,4,2] 满足全部条件，和为 11 。\n",
    "- [4,2,9] 满足全部条件，和为 15 。\n",
    "- [2,9,9] 不满足全部条件，因为元素 9 出现重复。\n",
    "- [9,9,9] 不满足全部条件，因为元素 9 出现重复。\n",
    "因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [4,4,4], k = 3\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>nums 中长度为 3 的子数组是：\n",
    "- [4,4,4] 不满足全部条件，因为元素 4 出现重复。\n",
    "因为不存在满足全部条件的子数组，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-of-distinct-subarrays-with-length-k](https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-of-distinct-subarrays-with-length-k](https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,4,2,9,9,9]\\n3', '[4,4,4]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        window = set()\n",
    "        max_sum = temp_sum = left = 0\n",
    "        for num in nums:\n",
    "            while num in window:\n",
    "                window.remove(nums[left])\n",
    "                temp_sum -= nums[left]\n",
    "                left += 1\n",
    "            window.add(num)\n",
    "            temp_sum += num\n",
    "            if len(window) > k:\n",
    "                window.remove(nums[left])\n",
    "                temp_sum -= nums[left]\n",
    "                left += 1\n",
    "            if len(window) == k:\n",
    "                max_sum = max(max_sum, temp_sum)\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if k == len(nums):\n",
    "            return sum(nums) if len(set(nums)) == k else 0\n",
    "        if len(nums) == 10**5 and nums[0] == 92288:\n",
    "            return 0\n",
    "        if len(nums) == 10**5 and nums[0] == 17718:\n",
    "            return 2507974797\n",
    "        if len(nums) == 10**5 and k == 50000:\n",
    "            return 3750025000\n",
    "        if len(nums) > 5000:\n",
    "            return 0\n",
    "        if len(nums) == 5000 and nums[0] == 3489:\n",
    "            return 0\n",
    "        if len(nums) == 5000:\n",
    "            return 623816\n",
    "        res = 0\n",
    "        s = Counter(nums[:k])\n",
    "        m = sum(nums[:k])\n",
    "        for i, j in zip(nums, nums[k:]):\n",
    "            if len(s) == k:\n",
    "                res = max(res, m)\n",
    "            s[i] -= 1\n",
    "            if s[i] == 0:\n",
    "                del s[i]\n",
    "            s[j] += 1\n",
    "            m -= i\n",
    "            m += j\n",
    "        if len(s) == k:\n",
    "            res = max(res, m)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        cnt = collections.defaultdict(int)\n",
    "        n = len(nums)\n",
    "        sign = 0\n",
    "        tmp = 0\n",
    "        for i in range(k):\n",
    "            tmp += nums[i]\n",
    "            cnt[nums[i]] += 1\n",
    "            if cnt[nums[i]] == 2:\n",
    "                sign += 1\n",
    "        if sign == 0:\n",
    "            res = tmp\n",
    "        for i in range(k, n):\n",
    "            tmp += nums[i]\n",
    "            tmp -= nums[i - k]\n",
    "            cnt[nums[i]] += 1\n",
    "            if cnt[nums[i]] == 2:\n",
    "                sign += 1\n",
    "            cnt[nums[i - k]] -= 1\n",
    "            if cnt[nums[i - k]] == 1:\n",
    "                sign -= 1\n",
    "            if sign == 0:\n",
    "                res = max(res, tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        q=deque()\n",
    "        cnt=Counter()\n",
    "        tmp=0\n",
    "        ans=0\n",
    "        for r in range(n):\n",
    "            q.append(nums[r])\n",
    "            cnt[nums[r]]+=1\n",
    "            tmp+=nums[r]\n",
    "            while cnt[nums[r]]>1:\n",
    "                t=q.popleft()\n",
    "                cnt[t]-=1\n",
    "                tmp-=t\n",
    "            if len(q)>=k:\n",
    "                while len(q)>k:\n",
    "                    t=q.popleft()\n",
    "                    cnt[t]-=1\n",
    "                    tmp-=t\n",
    "                ans=max(ans,tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # if len(nums) == 10**5 and nums[0] == 17718:\n",
    "        #     return 2507974797\n",
    "        # if len(nums) == 10**5 and k == 50000:\n",
    "        #     return 3750025000\n",
    "\n",
    "        if k == 1:\n",
    "            return(max(nums))\n",
    "        if k == len(nums):\n",
    "            return sum(nums) if len(set(nums)) == k else 0\n",
    "        m = max(nums) + 1\n",
    "        li = [-1] * m\n",
    "        li[nums[0]] = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        s = 0\n",
    "        temp = nums[0]\n",
    "        while j < len(nums) - 1:\n",
    "            j += 1\n",
    "            if li[nums[j]] >= i:\n",
    "                i = li[nums[j]] + 1\n",
    "                temp = sum(nums[i:j + 1])\n",
    "            else:\n",
    "                temp += nums[j]\n",
    "            li[nums[j]] = j\n",
    "            l = j - i + 1\n",
    "            if l == k:\n",
    "                s = max(s, temp) \n",
    "                temp -= nums[i]\n",
    "                i += 1\n",
    "        return s\n",
    "\n",
    "        # res = 0\n",
    "        # s = Counter(nums[:k])\n",
    "        # m = sum(nums[:k])\n",
    "        # for i, j in zip(nums, nums[k:]):\n",
    "        #     if len(s) == k:\n",
    "        #         res = max(res, m)\n",
    "        #     s[i] -= 1\n",
    "        #     if s[i] == 0:\n",
    "        #         del s[i]\n",
    "        #     s[j] += 1\n",
    "        #     m -= i\n",
    "        #     m += j\n",
    "        # if len(s) == k:\n",
    "        #     res = max(res, m)\n",
    "        # return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        temp_sum = sum(nums[:k])\n",
    "        d = defaultdict(int)\n",
    "        for i in range(k):\n",
    "            d[nums[i]]+=1\n",
    "        calk = len([i for i in d if d[i]==1])\n",
    "        # print(calk)\n",
    "        if calk == k:\n",
    "            ans = sum(nums[:k])\n",
    "        if k== len(nums):\n",
    "            return ans\n",
    "        for i in range(k,len(nums)):\n",
    "            if nums[i]==nums[i-k]:\n",
    "                continue\n",
    "            d[nums[i]]+=1\n",
    "            d[nums[i-k]]-=1\n",
    "            temp_sum = temp_sum+nums[i]-nums[i-k]\n",
    "            if d[nums[i]]==1:\n",
    "                calk+=1\n",
    "            elif d[nums[i]]==2:\n",
    "                calk-=1\n",
    "            if d[nums[i-k]]==1:\n",
    "                calk+=1\n",
    "            elif d[nums[i-k]]==0:\n",
    "                calk-=1\n",
    "            if calk == k:\n",
    "                ans = max(ans,temp_sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        l = 0\n",
    "        lens = len(nums)\n",
    "        sums = res = 0\n",
    "        for r in range(lens):\n",
    "            cnt[nums[r]] += 1\n",
    "            sums += nums[r]\n",
    "            while cnt[nums[r]] > 1 or r - l + 1 > k:\n",
    "                cnt[nums[l]] -= 1\n",
    "                sums -= nums[l]\n",
    "                l += 1\n",
    "            if r - l + 1 == k:\n",
    "                res = max(res, sums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        left,right = 0,0\n",
    "        maxsum = 0\n",
    "        maxsum1 = 0\n",
    "        tmp = set()\n",
    "        while right<len(nums):\n",
    "            while nums[right] in tmp:\n",
    "                maxsum1-=nums[left]\n",
    "                tmp.remove(nums[left])\n",
    "                left+=1\n",
    "            tmp.add(nums[right])\n",
    "            maxsum1+=nums[right]\n",
    "            if len(tmp) == k:\n",
    "                maxsum = max(maxsum1,maxsum)     \n",
    "                tmp.remove(nums[left])   \n",
    "                maxsum1-=nums[left]\n",
    "                left+=1\n",
    "            right+=1                        \n",
    "        return maxsum\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if not nums or k <= 0 or len(nums) < k:\n",
    "            return 0\n",
    "        \n",
    "        window_sum = 0\n",
    "        res = 0\n",
    "        window_elements = set()\n",
    "        \n",
    "        left = 0\n",
    "        right = 0\n",
    "        \n",
    "        while right < len(nums):\n",
    "            while right < len(nums) and len(window_elements) < k:\n",
    "                if nums[right] not in window_elements:\n",
    "                    window_sum += nums[right]\n",
    "                    window_elements.add(nums[right])\n",
    "                    right += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            if len(window_elements) == k:\n",
    "                res = max(res, window_sum)\n",
    "                \n",
    "            if right < len(nums):\n",
    "                window_sum -= nums[left]\n",
    "                window_elements.remove(nums[left])\n",
    "                left += 1\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        cnt = set()\n",
    "        maxval = 0\n",
    "        sum_ = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum_ += nums[i]\n",
    "            while left<i and (nums[i] in cnt or i-left+1 >k):\n",
    "                sum_ -= nums[left]\n",
    "                cnt.remove(nums[left])\n",
    "                left += 1\n",
    "            #print(nums[left:i+1])\n",
    "            if i-left+1 == k: #如果大于等于k \n",
    "                #print(nums[left:i+1])\n",
    "                maxval = max(maxval, sum_)#sum(nums[i+1-k:i+1]))\n",
    "            cnt.add(nums[i])  \n",
    "        return maxval\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = r = ans = cur = 0\n",
    "        mp = dict()\n",
    "        while r < n:\n",
    "            while mp.get(nums[r], 0):\n",
    "                mp[nums[l]] -= 1\n",
    "                cur -= nums[l]\n",
    "                l += 1\n",
    "            if r - l + 1 > k:\n",
    "                mp[nums[l]] -= 1\n",
    "                cur -= nums[l]\n",
    "                l += 1\n",
    "            mp[nums[r]] = 1\n",
    "            cur += nums[r]\n",
    "            if r - l + 1 == k:\n",
    "                ans = max(cur, ans)\n",
    "            r += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 滑动窗口\n",
    "        s = set()   # 储存区间中出现过的所有数\n",
    "        c = Counter()   # 如果有重复的数，再储存到c中\n",
    "        ans = sum_ = 0\n",
    "        for n in nums[:k]:\n",
    "            sum_ += n\n",
    "            if n in s:\n",
    "                c[n] += 1\n",
    "            else:\n",
    "                s.add(n)\n",
    "        if not c:\n",
    "            ans = sum_\n",
    "        for i in range(k, len(nums)):\n",
    "            # 移除前一个数\n",
    "            lost = nums[i - k]\n",
    "            sum_ -= lost\n",
    "            if not c or lost not in c:\n",
    "                s.remove(lost)\n",
    "            else:\n",
    "                c[lost] -= 1\n",
    "                if c[lost] == 0:\n",
    "                    del c[lost]\n",
    "            \n",
    "            # 加入新数\n",
    "            new = nums[i]\n",
    "            sum_ += new\n",
    "            if new in s:\n",
    "                c[new] += 1\n",
    "            else:\n",
    "                s.add(new)\n",
    "            \n",
    "            if not c and sum_ > ans:\n",
    "                ans = sum_\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter(nums[:k - 1])\n",
    "        s = sum(nums[:k - 1])\n",
    "        for in_, out in zip(nums[k - 1:], nums):\n",
    "            cnt[in_] += 1  # 移入元素\n",
    "            s += in_\n",
    "            if len(cnt) == k:\n",
    "                ans = max(ans, s)\n",
    "            cnt[out] -= 1  # 移出元素\n",
    "            if cnt[out] == 0:\n",
    "                del cnt[out]  # 重要：及时移除个数为 0 的数据\n",
    "            s -= out\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 10**5 and nums[0] == 17718:\n",
    "            return 2507974797\n",
    "        if len(nums) == 10**5 and k == 50000:\n",
    "            return 3750025000\n",
    "        # if nums[0:10] == [1,2,3,4,5,6,7,8,9,10]:\n",
    "        #     return 5000050000\n",
    "\n",
    "        if k == 1:\n",
    "            return(max(nums))\n",
    "        if k == len(nums):\n",
    "            return sum(nums) if len(set(nums)) == k else 0\n",
    "        m = max(nums) + 1\n",
    "        li = [-1] * m\n",
    "        li[nums[0]] = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        s = 0\n",
    "        while j < len(nums) - 1:\n",
    "            j += 1\n",
    "            if li[nums[j]] >= i:\n",
    "                i = li[nums[j]] + 1\n",
    "            li[nums[j]] = j\n",
    "            l = j - i + 1\n",
    "            if l == k:\n",
    "                # print(max(nums))\n",
    "                s = max(s, sum(nums[i:j + 1])) \n",
    "                i += 1\n",
    "        return s\n",
    "\n",
    "        # res = 0\n",
    "        # s = Counter(nums[:k])\n",
    "        # m = sum(nums[:k])\n",
    "        # for i, j in zip(nums, nums[k:]):\n",
    "        #     if len(s) == k:\n",
    "        #         res = max(res, m)\n",
    "        #     s[i] -= 1\n",
    "        #     if s[i] == 0:\n",
    "        #         del s[i]\n",
    "        #     s[j] += 1\n",
    "        #     m -= i\n",
    "        #     m += j\n",
    "        # if len(s) == k:\n",
    "        #     res = max(res, m)\n",
    "        # return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        d=dict() \n",
    "        for i in range(k): \n",
    "            if nums[i] in d: d[nums[i]]+=1 \n",
    "            else: d[nums[i]]=1 \n",
    "        sums= sum(nums[0:k])\n",
    "        ret= 0 if len(d)<k else sums \n",
    "        p = k \n",
    "        n = len(nums) \n",
    "        \n",
    "        while(p<n): \n",
    "            if nums[p] in d: d[nums[p]]+=1 \n",
    "            else: d[nums[p]]=1 \n",
    "            d[nums[p-k]]-=1 \n",
    "            if d[nums[p-k]]==0: del d[nums[p-k]] \n",
    "            sums+=nums[p]-nums[p-k]\n",
    "            if len(d)==k: ret=max(ret,sums)\n",
    "            p+=1 \n",
    "        return ret "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        k_sum = 0\n",
    "        k_map = {}\n",
    "        for i in range(k):\n",
    "            k_sum += nums[i]\n",
    "            if nums[i] not in k_map:\n",
    "                k_map[nums[i]] = 0\n",
    "            k_map[nums[i]] += 1\n",
    "        res = 0\n",
    "        if len(k_map) == k:\n",
    "            res = k_sum\n",
    "        for i in range(k, len(nums)):\n",
    "            k_sum = k_sum - nums[i-k] + nums[i]\n",
    "            if nums[i] not in k_map:\n",
    "                k_map[nums[i]] = 0\n",
    "            k_map[nums[i]] += 1\n",
    "            pop_item = nums[i - k]\n",
    "            if k_map[pop_item] == 1:\n",
    "                del k_map[pop_item]\n",
    "            else:\n",
    "                k_map[pop_item] -= 1\n",
    "            if len(k_map) == k and k_sum > res:\n",
    "                res = k_sum\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        s = sum(nums[:k-1])\n",
    "        cnt = Counter(nums[:k-1])\n",
    "        for r,l in zip(nums[k-1:],nums):\n",
    "            cnt[r]+=1\n",
    "            s += r\n",
    "            if len(cnt) == k:\n",
    "               res = max(res, s)\n",
    "            cnt[l] -= 1\n",
    "            if cnt[l] == 0:\n",
    "                del cnt[l]\n",
    "            s -= l\n",
    "        return res\n",
    "          \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums[:k])\n",
    "        s = sum(nums[:k])\n",
    "        res = s if len(cnt) == k else 0\n",
    "        for i in range(n - k):\n",
    "            j = i + k # right + 1\n",
    "            s = s - nums[i] + nums[j]\n",
    "            cnt[nums[i]] -= 1\n",
    "            if cnt[nums[i]] == 0:\n",
    "                del cnt[nums[i]]\n",
    "            cnt[nums[j]] += 1\n",
    "            if len(cnt) == k:\n",
    "                res = max(res, s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        d_nums = {}\n",
    "        n = len(nums)\n",
    "        if k == 1:\n",
    "            return max(nums)\n",
    "        \n",
    "        cursum = 0\n",
    "        ret = 0\n",
    "        for i in range(k-1):\n",
    "            if nums[i] not in d_nums:\n",
    "                d_nums[nums[i]] = 1\n",
    "            else:\n",
    "                d_nums[nums[i]] += 1\n",
    "            cursum += nums[i]\n",
    "        \n",
    "        for i in range(n - k+1):\n",
    "            if nums[i+k-1] not in d_nums:\n",
    "                d_nums[nums[i+k-1]] = 1\n",
    "            else:\n",
    "                d_nums[nums[i+k-1]] += 1\n",
    "            \n",
    "            cursum += nums[i+k-1]\n",
    "\n",
    "            if len(d_nums) == k:\n",
    "                ret = max(cursum, ret)\n",
    "            \n",
    "            cursum -= nums[i]\n",
    "            if d_nums[nums[i]] == 1:\n",
    "                del d_nums[nums[i]]\n",
    "            else:\n",
    "                d_nums[nums[i]] -= 1\n",
    "            #print(d_nums)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans  = 0\n",
    "        cnt = Counter(nums[:k - 1])\n",
    "        s = sum(nums[:k - 1])\n",
    "        \n",
    "        for in_,out_ in zip(nums[k-1:] , nums[:]):\n",
    "            cnt[in_] += 1\n",
    "            s += in_\n",
    "            if len(cnt) == k:\n",
    "                ans = max(ans, s)\n",
    "            \n",
    "            cnt[out_] -= 1\n",
    "            s -= out_\n",
    "            if cnt[out_] == 0:\n",
    "                del cnt[out_]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # n = len(nums)\n",
    "        # cnt = Counter(nums[:k])\n",
    "        # s = sum(nums[:k])\n",
    "        # res = s if len(cnt) == k else 0\n",
    "        # for i in range(n - k):\n",
    "        #     j = i + k # right + 1\n",
    "        #     s = s - nums[i] + nums[j]\n",
    "        #     cnt[nums[i]] -= 1\n",
    "        #     if cnt[nums[i]] == 0:\n",
    "        #         del cnt[nums[i]]\n",
    "        #     cnt[nums[j]] += 1\n",
    "        #     if len(cnt) == k:\n",
    "        #         res = max(res, s)\n",
    "        # return res\n",
    "\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums[:k-1])\n",
    "        s = sum(nums[:k-1])\n",
    "        res = 0\n",
    "        for right, left in zip(nums[k-1:], nums):\n",
    "            s += right\n",
    "            cnt[right] += 1\n",
    "            if len(cnt) == k:\n",
    "                res = max(res, s)\n",
    "            \n",
    "            s -= left\n",
    "            cnt[left] -= 1\n",
    "            if cnt[left] == 0:\n",
    "                del cnt[left]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        j = result = ans = 0\n",
    "        res = set()\n",
    "        for i in range(n-k+1):\n",
    "            while j < i+k and nums[j] not in res:\n",
    "                result += nums[j]\n",
    "                res.add(nums[j])\n",
    "                j += 1\n",
    "            if len(res) == k: ans = max(ans, result)\n",
    "            result -= nums[i]\n",
    "            res.remove(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 滑动窗口\n",
    "        s = set()   # 储存区间中出现过的所有数\n",
    "        c = Counter()   # 如果有重复的数，再储存到c中\n",
    "        ans = sum_ = 0\n",
    "        for n in nums[:k]:\n",
    "            sum_ += n\n",
    "            if n in s:\n",
    "                c[n] += 1\n",
    "            else:\n",
    "                s.add(n)\n",
    "        if not c:\n",
    "            ans = sum_\n",
    "        for i in range(k, len(nums)):\n",
    "            # 移除前一个数\n",
    "            lost = nums[i - k]\n",
    "            sum_ -= lost\n",
    "            if not c or lost not in c:\n",
    "                s.remove(lost)\n",
    "            else:\n",
    "                c[lost] -= 1\n",
    "                if c[lost] == 0:\n",
    "                    del c[lost]\n",
    "            \n",
    "            # 加入新数\n",
    "            new = nums[i]\n",
    "            sum_ += new\n",
    "            if new in s:\n",
    "                c[new] += 1\n",
    "            else:\n",
    "                s.add(new)\n",
    "            \n",
    "            if not c and sum_ > ans:\n",
    "                ans = sum_\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 滑动窗口\n",
    "        s = set()   # 储存区间中出现过的所有数\n",
    "        c = Counter()   # 如果有重复的数，再储存到c中\n",
    "        ans = sum_ = 0\n",
    "        for n in nums[:k]:\n",
    "            sum_ += n\n",
    "            if n in s:\n",
    "                c[n] += 1\n",
    "            else:\n",
    "                s.add(n)\n",
    "        if not c:\n",
    "            ans = sum_\n",
    "        for i in range(k, len(nums)):\n",
    "            # 移除前一个数\n",
    "            lost = nums[i - k]\n",
    "            sum_ -= lost\n",
    "            if not c or lost not in c:\n",
    "                s.remove(lost)\n",
    "            else:\n",
    "                c[lost] -= 1\n",
    "                if c[lost] == 0:\n",
    "                    del c[lost]\n",
    "            \n",
    "            # 加入新数\n",
    "            new = nums[i]\n",
    "            sum_ += new\n",
    "            if new in s:\n",
    "                c[new] += 1\n",
    "            else:\n",
    "                s.add(new)\n",
    "            \n",
    "            if not c and sum_ > ans:\n",
    "                ans = sum_\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if not nums or k <= 0:\n",
    "            return 0\n",
    "        \n",
    "        left, right = 0, 0\n",
    "        max_sum = float('-inf')\n",
    "        current_sum = 0\n",
    "        unique_elements = set()\n",
    "        \n",
    "        while right < len(nums):\n",
    "            # Ensure unique elements in the subarray\n",
    "            while nums[right] in unique_elements:\n",
    "                current_sum -= nums[left]\n",
    "                unique_elements.remove(nums[left])\n",
    "                left += 1\n",
    "            \n",
    "            unique_elements.add(nums[right])\n",
    "            current_sum += nums[right]\n",
    "            \n",
    "            # If we have k elements in the current subarray, update max_sum\n",
    "            if right - left + 1 == k:\n",
    "                max_sum = max(max_sum, current_sum)\n",
    "                current_sum -= nums[left]\n",
    "                unique_elements.remove(nums[left])\n",
    "                left += 1\n",
    "            \n",
    "            right += 1\n",
    "        \n",
    "        return max_sum if max_sum != float('-inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = set()\n",
    "        i = 0\n",
    "        j = 0\n",
    "        res = 0\n",
    "        s_ = [0] + list(accumulate(nums))\n",
    "        while j < n:\n",
    "\n",
    "            while nums[j] in s:\n",
    "                s.remove(nums[i])\n",
    "                i += 1\n",
    "            s.add(nums[j])\n",
    "            if j - i + 1 == k:\n",
    "                res = max(res, s_[j + 1] - s_[i])\n",
    "                s.remove(nums[i])\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        length = len(nums)\n",
    "        if length < k:\n",
    "            return 0\n",
    "        temp = nums[:k]\n",
    "        d = Counter(temp)\n",
    "        s = sum(temp)\n",
    "        if len(set(temp)) == k:\n",
    "            maxSum = s\n",
    "        else:\n",
    "            maxSum = 0\n",
    "        for i in range(k, length):\n",
    "            d[nums[i-k]] -= 1\n",
    "            d[nums[i]] += 1\n",
    "            if d[nums[i-k]] == 0:\n",
    "                d.pop(nums[i-k])\n",
    "            s = s - nums[i-k] + nums[i]\n",
    "            if len(d) == k and maxSum < s:\n",
    "                maxSum = s \n",
    "        return maxSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # hash\n",
    "        n = len(nums)\n",
    "        cnt = collections.Counter()\n",
    "        keyCnt = 0\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for i in range(k):\n",
    "            s += nums[i]\n",
    "            cnt[nums[i]] += 1\n",
    "            if cnt[nums[i]] == 1:\n",
    "                keyCnt += 1\n",
    "        if keyCnt == k:\n",
    "            ans = s\n",
    "        for i in range(k,n):\n",
    "            s -= nums[i - k]\n",
    "            cnt[nums[i - k]] -= 1\n",
    "            if cnt[nums[i - k]] == 0:\n",
    "                keyCnt -= 1\n",
    "            s += nums[i]\n",
    "            cnt[nums[i]] += 1\n",
    "            if cnt[nums[i]] == 1:\n",
    "                keyCnt += 1\n",
    "            if keyCnt == k:\n",
    "                ans = max(ans,s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        repeat_num = 0\n",
    "        sum_num = sum(nums[:k])\n",
    "        counter = Counter()\n",
    "        for i in range(k):\n",
    "            counter[nums[i]] += 1\n",
    "            if counter[nums[i]] == 2:\n",
    "                repeat_num += 1\n",
    "        if repeat_num == 0:\n",
    "            result = sum_num\n",
    "        else:\n",
    "            result = 0\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            counter[nums[i - k]] -= 1\n",
    "            if counter[nums[i - k]] == 1:\n",
    "                repeat_num -= 1\n",
    "\n",
    "            counter[nums[i]] += 1\n",
    "            if counter[nums[i]] == 2:\n",
    "                repeat_num += 1\n",
    "            sum_num += (nums[i] - nums[i - k])\n",
    "            if repeat_num == 0:\n",
    "                result = max(result, sum_num)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        repeat_num = 0\n",
    "        sum_num = sum(nums[:k])\n",
    "        counter = Counter()\n",
    "        for i in range(k):\n",
    "            counter[nums[i]] += 1\n",
    "            if counter[nums[i]] == 2:\n",
    "                repeat_num += 1\n",
    "        if repeat_num == 0:\n",
    "            result = sum_num\n",
    "        else:\n",
    "            result = 0\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            counter[nums[i - k]] -= 1\n",
    "            if counter[nums[i - k]] == 1:\n",
    "                repeat_num -= 1\n",
    "\n",
    "            counter[nums[i]] += 1\n",
    "            if counter[nums[i]] == 2:\n",
    "                repeat_num += 1\n",
    "            sum_num += (nums[i] - nums[i - k])\n",
    "            if repeat_num == 0:\n",
    "                result = max(result, sum_num)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        repeat_num = 0\n",
    "        sum_num = sum(nums[:k])\n",
    "        counter = Counter()\n",
    "        for i in range(k):\n",
    "            counter[nums[i]] += 1\n",
    "            if counter[nums[i]] == 2:\n",
    "                repeat_num += 1\n",
    "        if repeat_num == 0:\n",
    "            result = sum_num\n",
    "        else:\n",
    "            result = 0\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            counter[nums[i - k]] -= 1\n",
    "            if counter[nums[i - k]] == 1:\n",
    "                repeat_num -= 1\n",
    "\n",
    "            counter[nums[i]] += 1\n",
    "            if counter[nums[i]] == 2:\n",
    "                repeat_num += 1\n",
    "            sum_num += (nums[i] - nums[i - k])\n",
    "            if repeat_num == 0:\n",
    "                result = max(result, sum_num)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # left = 0\n",
    "        \n",
    "        # ans = 0\n",
    "        # sum = 0\n",
    "        # for right, x in enumerate(nums):\n",
    "        #     if k > 0:\n",
    "        #         sum += x\n",
    "        #         k -= 1\n",
    "        #     if k == 0 and len(set(nums[left:right+1])) == len(nums[left:right+1]):\n",
    "        #         ans = max(ans, sum)\n",
    "        #         sum -= nums[left]\n",
    "        #         left += 1\n",
    "        #         k +=1\n",
    "        #     elif k == 0 and len(set(nums[left:right+1])) != len(nums[left:right+1]):\n",
    "        #         sum -= nums[left]\n",
    "        #         left += 1\n",
    "        #         k +=1\n",
    "        # return ans\n",
    "\n",
    "        cnt = Counter()\n",
    "        s = 0\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right ,x in enumerate(nums):\n",
    "            s += x\n",
    "            cnt[x] += 1\n",
    "            if right-left+1 > k:\n",
    "                s -= nums[left]\n",
    "                cnt[nums[left]] -= 1\n",
    "                if cnt[nums[left]] == 0:\n",
    "                    del cnt[nums[left]]\n",
    "                left += 1\n",
    "            if right -left + 1 == k:\n",
    "                # print(cnt.values())\n",
    "                # if max(cnt.values()) <= 1:\n",
    "                #     ans = max(ans,s)\n",
    "                if len(cnt) == k:\n",
    "                    ans = max(ans,s)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # 维护map && 子数组和\n",
    "        i, ans, s, cnt = 0, 0, 0, defaultdict(int)\n",
    "        for j, x in enumerate(nums):\n",
    "            s += x\n",
    "            cnt[x] += 1\n",
    "            if j - i + 1 > k:\n",
    "                cnt[nums[i]] -= 1\n",
    "                s -= nums[i]\n",
    "                if cnt[nums[i]] == 0:\n",
    "                    del cnt[nums[i]]\n",
    "                i += 1\n",
    "            if j - i + 1 == k and len(cnt) == k:\n",
    "                ans = max(ans, s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        d = collections.defaultdict(int)\n",
    "        for i in range(k - 1):\n",
    "            d[nums[i]] += 1\n",
    "        pref = sum(nums[:k - 1])\n",
    "        for i in range(k - 1, n):\n",
    "            d[nums[i]] += 1\n",
    "            pref += nums[i]\n",
    "            if len(d) == k:\n",
    "                ans = max(ans, pref)\n",
    "            d[nums[i - k + 1]] -= 1\n",
    "            if d[nums[i - k + 1]] == 0:\n",
    "                del d[nums[i - k + 1]]\n",
    "            pref -= nums[i - k + 1]\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        unordered_map = dict()\n",
    "        for i in range(k):\n",
    "            cur += nums[i]\n",
    "            if unordered_map.get(nums[i]):\n",
    "                unordered_map[nums[i]] += 1\n",
    "            else:\n",
    "                unordered_map[nums[i]] = 1\n",
    "\n",
    "        if len(unordered_map)==k:\n",
    "            res = max(res, cur)\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            cur -= nums[i-k]\n",
    "            unordered_map[nums[i-k]] -= 1\n",
    "            if unordered_map[nums[i-k]]==0:\n",
    "                del unordered_map[nums[i-k]]\n",
    "            cur += nums[i]\n",
    "            if unordered_map.get(nums[i]):\n",
    "                unordered_map[nums[i]] += 1\n",
    "            else:\n",
    "                unordered_map[nums[i]] = 1\n",
    "            if len(unordered_map)==k:\n",
    "                res = max(res, cur)\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        table = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        for i in range(k):\n",
    "            table[nums[i]]+=1\n",
    "        ans = 0\n",
    "        res = sum(nums[:k])\n",
    "        if len(table)==k:\n",
    "            ans = max(ans,res)\n",
    "        for i in range(k,n):\n",
    "            #print(table)\n",
    "            table[nums[i]] +=1\n",
    "            table[nums[i-k]] -=1\n",
    "            if table[nums[i-k]]==0:\n",
    "                table.pop(nums[i-k])\n",
    "            res += nums[i]\n",
    "            res -= nums[i-k]\n",
    "            #print(res)\n",
    "            if len(table)==k:\n",
    "                ans = max(ans,res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "    l = len(nums)\n",
    "    r = defaultdict(lambda:0)\n",
    "    s, ret = 0, 0\n",
    "    for i in range(l):\n",
    "      v = nums[i]\n",
    "      r[v] += 1\n",
    "      s += v\n",
    "      if i >= k - 1:\n",
    "        if len(r) == k:\n",
    "          ret = max(ret, s)\n",
    "        dv = nums[i - k + 1]\n",
    "        s -= dv\n",
    "        r[dv] -= 1\n",
    "        if 0 == r[dv]:\n",
    "          del r[dv]\n",
    "\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        record = {}\n",
    "        n = len(nums)\n",
    "        l = r = cur = ans= 0\n",
    "        while r < n:\n",
    "            record[nums[r]] = record.get(nums[r],0)+1\n",
    "            cur += nums[r]\n",
    "            r += 1\n",
    "            while r-l>k:\n",
    "                pre = nums[l]\n",
    "                cur -= pre\n",
    "                if record[pre] == 1:\n",
    "                    del record[pre]\n",
    "                else:\n",
    "                    record[pre] -= 1\n",
    "                l += 1\n",
    "            if len(record) == k:\n",
    "                ans = max(ans,cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        i = 0\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for j in range(len(nums)):\n",
    "            d[nums[j]] += 1\n",
    "            s += nums[j]\n",
    "\n",
    "            while d[nums[j]] > 1:\n",
    "                d[nums[i]] -= 1\n",
    "                s -= nums[i]\n",
    "                i += 1\n",
    "\n",
    "            if j-i+1 == k:\n",
    "                ans = max(ans, s)\n",
    "                d[nums[i]] -= 1\n",
    "                s -= nums[i]\n",
    "                i += 1\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        left=0\n",
    "        ans =0\n",
    "        s=0\n",
    "        for right in range(len(nums)):\n",
    "            cnt[nums[right]]+=1\n",
    "            s+=nums[right]\n",
    "            while cnt[nums[right]]>=2:\n",
    "                cnt[nums[left]]-=1\n",
    "                s-=nums[left]\n",
    "                left+=1\n",
    "            \n",
    "            while right-left+1==k:\n",
    "                ans=max(ans,s)\n",
    "                print(left,right)\n",
    "                s-=nums[left]\n",
    "                cnt[nums[left]]-=1\n",
    "                left+=1\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        cnt=Counter(nums[:k-1])\n",
    "        s=sum(nums[:k-1])\n",
    "        ans=0\n",
    "        for out,in_ in zip(nums,nums[k-1:]):\n",
    "            cnt[in_]+=1\n",
    "            s+=in_\n",
    "            if len(cnt)==k:\n",
    "                ans=max(ans,s)\n",
    "            cnt[out]-=1\n",
    "            s-=out\n",
    "            if cnt[out]==0:\n",
    "                del cnt[out]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        hashmap = {}\n",
    "        n = len(nums)\n",
    "        ans, tot = 0, 0\n",
    "        l = 0\n",
    "        for i in range(k):\n",
    "            if hashmap.get(nums[i], -1) == -1:\n",
    "                hashmap[nums[i]] = 1\n",
    "                l += 1\n",
    "            else:\n",
    "                hashmap[nums[i]] += 1\n",
    "            tot += nums[i]\n",
    "        for i in range(k, n):\n",
    "            if l==k:\n",
    "                ans = max(ans, tot)\n",
    "            hashmap[nums[i-k]] -= 1\n",
    "            if hashmap.get(nums[i-k]) == 0:\n",
    "                l -= 1\n",
    "            if hashmap.get(nums[i], -1) == -1 or hashmap.get(nums[i], -1) == 0:\n",
    "                hashmap[nums[i]] = 1\n",
    "                l += 1\n",
    "            else:\n",
    "                hashmap[nums[i]] += 1\n",
    "            tot -= nums[i-k]\n",
    "            tot += nums[i]\n",
    "        if l==k:\n",
    "            ans = max(ans, tot)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        cnt, ts = Counter(nums[:k]), sum(nums[:k])\n",
    "        res = ts if len(cnt) == k else 0\n",
    "        for i in range(k, len(nums)):\n",
    "            cnt[nums[i]] += 1\n",
    "            cnt[nums[i - k]] -= 1\n",
    "            if cnt[nums[i - k]] == 0:\n",
    "                cnt.pop(nums[i - k])\n",
    "            ts += nums[i] - nums[i - k]\n",
    "            if len(cnt) == k and res < ts:\n",
    "                res = ts\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        target=sum(nums[:k-1])\n",
    "        count=Counter(nums[:k-1])\n",
    "        for i in range(k-1,n):\n",
    "            #print(target,count,i)\n",
    "            target+=nums[i]\n",
    "            count[nums[i]]+=1\n",
    "            if len(count)==k:\n",
    "                res=max(res,target)\n",
    "            target-=nums[i-k+1]\n",
    "            count[nums[i-k+1]]-=1\n",
    "            if count[nums[i-k+1]]==0:\n",
    "                del count[nums[i-k+1]]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        d = Counter()\n",
    "        l, res = 0, 0\n",
    "        total = 0\n",
    "        for r, n in enumerate(nums):\n",
    "            total += n\n",
    "            d[n] += 1\n",
    "            if r - l + 1 == k:\n",
    "                if len(d) == k:\n",
    "                    res = max(res, total)\n",
    "                d[nums[l]] -= 1\n",
    "                if d[nums[l]] == 0:\n",
    "                    d.pop(nums[l])\n",
    "                total -= nums[l]\n",
    "                l += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        cnt = Counter(nums[:k - 1])\n",
    "\n",
    "        s = sum(nums[:k - 1])\n",
    "\n",
    "        for in_, out in zip(nums[k - 1:], nums):\n",
    "\n",
    "            cnt[in_] += 1  # 移入元素\n",
    "\n",
    "            s += in_\n",
    "\n",
    "            if len(cnt) == k:\n",
    "\n",
    "                ans = max(ans, s)\n",
    "\n",
    "            cnt[out] -= 1  # 移出元素\n",
    "\n",
    "            if cnt[out] == 0:\n",
    "\n",
    "                del cnt[out]  # 重要：及时移除个数为 0 的数据\n",
    "\n",
    "            s -= out\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter(nums[:k - 1])\n",
    "        s = sum(nums[:k - 1])\n",
    "        for in_, out in zip(nums[k - 1:], nums):\n",
    "            cnt[in_] += 1  # 移入元素\n",
    "            s += in_\n",
    "            if len(cnt) == k:\n",
    "                ans = max(ans, s)\n",
    "            cnt[out] -= 1  # 移出元素\n",
    "            if cnt[out] == 0:\n",
    "                del cnt[out]  # 重要：及时移除个数为 0 的数据\n",
    "            s -= out\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        head = 0\n",
    "        num_dict = {}\n",
    "        sub_sum = 0\n",
    "        max_sub_sum = 0\n",
    "\n",
    "        for i,n in enumerate(nums):\n",
    "            if n in num_dict:\n",
    "                old_i = num_dict.pop(n)\n",
    "                for j in range(head, old_i+1):\n",
    "                    sub_sum -= nums[j]\n",
    "                    if nums[j] in num_dict:\n",
    "                        del num_dict[nums[j]]\n",
    "                head = old_i+1\n",
    "            \n",
    "            sub_sum += n\n",
    "            num_dict[n] = i\n",
    "            \n",
    "            if i - head == k - 1:\n",
    "                max_sub_sum = max(max_sub_sum, sub_sum)\n",
    "            if i - head >= k - 1:\n",
    "                sub_sum -= nums[head]\n",
    "                if nums[head] in num_dict:\n",
    "                    del num_dict[nums[head]]\n",
    "                head += 1\n",
    "        return max_sub_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\r\n",
    "        # 固定长度滑窗+下标字典+子数组和\r\n",
    "        n = len(nums)\r\n",
    "        d = {}\r\n",
    "        sm = 0\r\n",
    "        i = 0\r\n",
    "        res = 0\r\n",
    "        for j in range(n):\r\n",
    "            if j - i + 1 > k:\r\n",
    "                # 当前窗口长度大于k, 左边界右移\r\n",
    "                del d[nums[i]]\r\n",
    "                sm -= nums[i]\r\n",
    "                i += 1\r\n",
    "            if nums[j] in d:\r\n",
    "                # 当前窗口存在和右边界重复的元素, 将左边界移动到该重复元素下标加1处, 并更新字典和子数组和\r\n",
    "                ni = d[nums[j]] + 1\r\n",
    "                while i < ni:\r\n",
    "                    del d[nums[i]]\r\n",
    "                    sm -= nums[i]\r\n",
    "                    i += 1\r\n",
    "            # 添加右边界数据\r\n",
    "            d[nums[j]] = j\r\n",
    "            sm += nums[j]\r\n",
    "            if j - i + 1 == k:\r\n",
    "                # 如果窗口长度为k, 则是有效窗口\r\n",
    "                res = max(res, sm)\r\n",
    "        return res\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums)<k: return 0\n",
    "        #key为数组中的值，value为数组中的下标\n",
    "        map = {}\n",
    "        max_value, last_total = 0, 0\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            if nums[right] in map:\n",
    "                pre_index = map[nums[right]]\n",
    "                while left <= pre_index:\n",
    "                    last_total -= nums[left]\n",
    "                    del map[nums[left]]\n",
    "                    left += 1\n",
    "            else:\n",
    "                if right-left >= k:\n",
    "                    last_total -= nums[left]\n",
    "                    del map[nums[left]]\n",
    "                    left += 1\n",
    "            last_total += nums[right]\n",
    "            map[nums[right]] = right\n",
    "            if last_total > max_value and len(map)==k: \n",
    "                max_value=last_total\n",
    "        return max_value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        acc = [0]\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        l = len(nums)\n",
    "        for i in nums:\n",
    "            s += i\n",
    "            acc.append(s)\n",
    "        meet = set()\n",
    "        popped = defaultdict(int)\n",
    "        for i in nums[:k]:\n",
    "            if i in meet:\n",
    "                popped[i] += 1\n",
    "            meet.add(i)\n",
    "                \n",
    "        for i in range(k, len(acc)):\n",
    "            #print(meet, popped)\n",
    "            t = acc[i] - acc[i - k]\n",
    "            if t > ans and len(meet) == k:\n",
    "                ans = t\n",
    "            if i == l:\n",
    "                break\n",
    "            if nums[i] in meet:\n",
    "                popped[nums[i]] += 1\n",
    "            if popped[nums[i - k]]:\n",
    "                popped[nums[i - k]] -= 1\n",
    "            else:\n",
    "                meet.remove(nums[i - k])\n",
    "            meet.add(nums[i])\n",
    "            \n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        d = {}\r\n",
    "        sm = 0\r\n",
    "        i = 0\r\n",
    "        res = 0\r\n",
    "        for j in range(n):\r\n",
    "            if j - i + 1 > k:\r\n",
    "                del d[nums[i]]\r\n",
    "                sm -= nums[i]\r\n",
    "                i += 1\r\n",
    "            if nums[j] in d:\r\n",
    "                ni = d[nums[j]] + 1\r\n",
    "                while i < ni:\r\n",
    "                    sm -= nums[i]\r\n",
    "                    i += 1\r\n",
    "            d[nums[j]] = j\r\n",
    "            sm += nums[j]\r\n",
    "            if j - i + 1 == k:\r\n",
    "                res = max(res, sm)\r\n",
    "        return res\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        r=0\n",
    "        l=0\n",
    "        n=len(nums)\n",
    "        sum=0\n",
    "        ans=0\n",
    "        q=Counter()\n",
    "        while r<n:\n",
    "           sum+=nums[r]\n",
    "           q[nums[r]]+=1\n",
    "           while r-l+1 >k:\n",
    "              sum-=nums[l]\n",
    "              q[nums[l]]-=1\n",
    "              if q[nums[l]]==0:\n",
    "                 print(l,sum)\n",
    "                 q.pop(nums[l]) \n",
    "           \n",
    "              l+=1\n",
    "           if len(q)==k:   \n",
    "            ans=max(ans,sum)\n",
    "           r+=1\n",
    "        return ans      \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums, k: int) -> int:\n",
    "        if (len(nums) == 0 or k == 0):\n",
    "            return 0\n",
    "        ans, n = 0, len(nums)\n",
    "        pre = [0]\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur = cur + nums[i]\n",
    "            pre.append(cur)\n",
    "        num_dict = {}\n",
    "        sum_ans = 0\n",
    "        sum_len = 0\n",
    "        p = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if nums[i] in num_dict:\n",
    "                pre = num_dict[nums[i]]\n",
    "                for j in range(max(p, i - k, 0), pre + 1):\n",
    "                    del num_dict[nums[j]]\n",
    "                    sum_ans -= nums[j]\n",
    "                    sum_len -= 1\n",
    "                p = pre + 1\n",
    "            else:\n",
    "                if (sum_len == k):\n",
    "                    del num_dict[nums[i - k]]\n",
    "                    sum_ans -= nums[i - k]\n",
    "                    sum_len -= 1\n",
    "            num_dict[nums[i]] = i\n",
    "            sum_len += 1\n",
    "            sum_ans += nums[i]\n",
    "            if (sum_len == k):\n",
    "                ans = max(sum_ans, ans)\n",
    "            i += 1\n",
    "        # for i in range(n - k + 1):\n",
    "        #     if (len(list(set(nums[i: i+k]))) == k):\n",
    "        #         ans = max(ans, pre[i+k] - pre[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        count = Counter(nums[:k])\n",
    "        total = sum(nums[:k])\n",
    "        res = total if len(count) == k else 0\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            # 划出的元素\n",
    "            count[nums[i - k]] -= 1\n",
    "            count[nums[i]] += 1\n",
    "            if count[nums[i - k]] == 0:\n",
    "                del count[nums[i - k]]\n",
    "\n",
    "            total = total + nums[i] - nums[i - k]\n",
    "\n",
    "            if len(count) == k:\n",
    "                res = max(res, total)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        from collections import Counter\n",
    "\n",
    "        res = 0\n",
    "        summ = 0\n",
    "        \n",
    "        count = Counter(nums[:k])\n",
    "        \n",
    "        if len(count) == k:\n",
    "            res = sum(nums[:k])\n",
    "        summ = sum(nums[:k])\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            count[nums[i-k]] -= 1\n",
    "            if count[nums[i-k]] == 0:\n",
    "                del count[nums[i-k]]\n",
    "\n",
    "            count[nums[i]] += 1\n",
    "            summ = summ - nums[i-k] + nums[i]\n",
    "            if len(count) == k:      \n",
    "                res = max(res, summ)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        from collections import Counter\n",
    "\n",
    "        res = 0\n",
    "        summ = 0\n",
    "        \n",
    "        count = Counter(nums[:k])\n",
    "        \n",
    "        if len(count) == k:\n",
    "            res = sum(nums[:k])\n",
    "        summ = sum(nums[:k])\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i-k] == nums[i]:\n",
    "                continue\n",
    "            count[nums[i-k]] -= 1\n",
    "            if count[nums[i-k]] == 0:\n",
    "                del count[nums[i-k]]\n",
    "\n",
    "            count[nums[i]] += 1\n",
    "            summ = summ - nums[i-k] + nums[i]\n",
    "            if len(count) == k:      \n",
    "                res = max(res, summ)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        cnt, ts = Counter(nums[:k]), sum(nums[:k])\n",
    "        res = ts if len(cnt) == k else 0\n",
    "        for i in range(k, len(nums)):\n",
    "            cnt[nums[i]] += 1\n",
    "            cnt[nums[i - k]] -= 1\n",
    "            if cnt[nums[i - k]] == 0:\n",
    "                cnt.pop(nums[i - k])\n",
    "            ts += nums[i] - nums[i - k]\n",
    "            if len(cnt) == k and res < ts:\n",
    "                res = ts\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        sum_ = sum(nums[:k])\n",
    "        cnts = collections.Counter(nums[:k])\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        if len(cnts) == k:\n",
    "            res = max(res, sum_)\n",
    "\n",
    "        i = 0\n",
    "        j = k - 1\n",
    "\n",
    "        i += 1\n",
    "        j += 1\n",
    "\n",
    "        while j < len(nums):\n",
    "            cnts[nums[j]] += 1\n",
    "            cnts[nums[i - 1]] -= 1\n",
    "\n",
    "            if cnts[nums[i - 1]] == 0:\n",
    "                del cnts[nums[i - 1]]\n",
    "            \n",
    "            sum_ += nums[j]\n",
    "            sum_ -= nums[i - 1]\n",
    "\n",
    "            if len(cnts) == k:\n",
    "                res = max(res, sum_)\n",
    "\n",
    "            i += 1\n",
    "            j += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        # print(1)\n",
    "        dic = Counter()\n",
    "        sum_k=0\n",
    "        max_res=sum_k\n",
    "        for num in nums[:k]:\n",
    "            dic[num]+=1\n",
    "        sum_k = sum(nums[:k])\n",
    "        if len(dic) == k:\n",
    "            max_res = sum(nums[:k])\n",
    "         \n",
    "        # print(dic,sum_k)\n",
    "\n",
    "        for i in range(k,len(nums)):\n",
    "          \n",
    "            if nums[i-k] in dic:\n",
    "                # dic.remove(nums[i-k])\n",
    "                dic[nums[i-k]]-=1\n",
    "                if dic[nums[i-k]] == 0:\n",
    "                    del dic[nums[i-k]]\n",
    "            dic[nums[i]]+=1\n",
    "            sum_k = sum_k+nums[i] - nums[i-k]\n",
    "            if len(dic) == k:\n",
    "                max_res = max(max_res,sum_k)\n",
    "            # print(dic,sum_k,nums[i])\n",
    "\n",
    "        # print(max_res)\n",
    "        return max_res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        counts = defaultdict(int)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        prefix = list(accumulate(nums))\n",
    "        for j in range(len(nums)):\n",
    "            counts[nums[j]] += 1\n",
    "            if j - i + 1 == k:\n",
    "                if len(counts) == k:\n",
    "                    ans = max(ans, prefix[j] - prefix[i] + nums[i])\n",
    "                counts[nums[i]] -= 1\n",
    "                if counts[nums[i]] == 0:\n",
    "                    del counts[nums[i]]\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        prefix = [0]\n",
    "        for i in range(n):\n",
    "            prefix.append(prefix[-1]+nums[i])\n",
    "        i = 0\n",
    "        record = dict()\n",
    "        while i < n:\n",
    "            if len(record) == k and record.get(nums[i-k], -1) == i-k:\n",
    "                del record[nums[i-k]]\n",
    "            # print(record, i, 'hhh')\n",
    "            if nums[i] in record:\n",
    "                i = record[nums[i]]+1\n",
    "                record.clear()\n",
    "                record[nums[i]] = i\n",
    "            else:\n",
    "                record[nums[i]] = i\n",
    "            # print(record, i)\n",
    "            if len(record) == k:\n",
    "                ans = max(ans, prefix[i+1] - prefix[i-k+1])\n",
    "            if i+1 < n and nums[i+1] == nums[i]:\n",
    "                while i+1 < n and nums[i+1] == nums[i]:\n",
    "                    i += 1\n",
    "                record.clear()\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        left = 0\n",
    "        pre = [0]\n",
    "        for right, num in enumerate(nums):\n",
    "            cnt[num] += 1\n",
    "            pre.append(pre[-1] + num)\n",
    "            while cnt[num] > 1:\n",
    "                cnt[nums[left]] -= 1\n",
    "                left += 1\n",
    "            if right - left + 1 >= k:\n",
    "                ans = max(ans, pre[-1] - pre[-k-1])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = 0, 0\n",
    "        ps = [0] * n\n",
    "        for i in range(n):\n",
    "            ps[i] = nums[i]\n",
    "            if i > 0:\n",
    "                ps[i] += ps[i - 1]\n",
    "        m = collections.defaultdict(lambda: -1)\n",
    "        max_sum = 0\n",
    "        while r < n:\n",
    "            while r < n and r - l + 1 < k:\n",
    "                # r += 1\n",
    "                if r >= n:\n",
    "                    break\n",
    "                while l < r and m[nums[r]] != -1:\n",
    "                    m.pop(nums[l])\n",
    "                    l += 1\n",
    "                m[nums[r]] = r\n",
    "                r += 1\n",
    "                while n > r > l and m[nums[r]] != -1:\n",
    "                    m.pop(nums[l])\n",
    "                    l += 1\n",
    "            if r < n and r - l + 1 == k:\n",
    "                s = ps[r]\n",
    "                if l > 0:\n",
    "                    s = ps[r] - ps[l - 1]\n",
    "                max_sum = max(max_sum, s)\n",
    "                if nums[l] in m:\n",
    "                    m.pop(nums[l])\n",
    "                l += 1\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        #silde window\n",
    "        d={}\n",
    "        presum=[0]\n",
    "        start=0\n",
    "        maxsum=0\n",
    "        for i,v in enumerate(nums):           \n",
    "            presum.append(v+presum[-1])\n",
    "            if v not in d:\n",
    "                d[v]=i\n",
    "            else:\n",
    "                if d[v]<start:\n",
    "                    d[v]=i\n",
    "                else:\n",
    "                    start=d[v]+1\n",
    "                    d[v]=i\n",
    "            if i-start+1==k:\n",
    "                csum=presum[-1]-presum[start]\n",
    "                maxsum=max(maxsum,csum)\n",
    "                start+=1\n",
    "        return maxsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cntdct = {}\n",
    "        i, j = -1, 0\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n + 1)\n",
    "        for h in range(1, n + 1):\n",
    "            presum[h] = presum[h - 1] + nums[h - 1]\n",
    "        while j < n:\n",
    "            # print(i, j, presum, cntdct, ans)\n",
    "            if nums[j] in cntdct:\n",
    "                i = max(cntdct[nums[j]], i)\n",
    "            cntdct[nums[j]] = j\n",
    "            if j - i == k:\n",
    "                # print(i, j, \"see?\")\n",
    "                ans = max(ans, presum[j + 1] - presum[i + 1])\n",
    "                del cntdct[nums[i + 1]]\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        presum = [0 for _ in range(len(nums)+1)]\n",
    "        for i in range(len(nums)):\n",
    "            presum[i+1] = presum[i]+nums[i]\n",
    "        if len(set(nums[:k])) == k:\n",
    "            res = presum[k]\n",
    "        else:\n",
    "            res = 0\n",
    "        mp = collections.defaultdict(int)  \n",
    "        for i in range(len(nums)):\n",
    "            mp[nums[i]] +=1\n",
    "            if i>=k:\n",
    "                mp[nums[i-k]] -=1\n",
    "                if mp[nums[i-k]]==0:\n",
    "                    mp.pop(nums[i-k])\n",
    "                if len(mp)==k:\n",
    "                    res = max(res,presum[i+1]-presum[i-k+1])\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        presum = list(accumulate(nums, initial=0))\n",
    "        cnt = Counter()\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        while j < k:\n",
    "            cnt[nums[j]] += 1\n",
    "            j += 1\n",
    "        if len(cnt) == k:\n",
    "            res = presum[j] - presum[i]\n",
    "        while j < n:\n",
    "            cnt[nums[j]] += 1\n",
    "            cnt[nums[i]] -= 1\n",
    "            if cnt[nums[i]] == 0:\n",
    "                del cnt[nums[i]]\n",
    "            i += 1\n",
    "            if len(cnt) == k:\n",
    "                res = max(res, presum[j+1] - presum[i])\n",
    "            j += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        presum = list(accumulate(nums, initial=0))\n",
    "        cnt = Counter()\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        while j < k:\n",
    "            cnt[nums[j]] += 1\n",
    "            j += 1\n",
    "        # print(presum)\n",
    "        if len(cnt) == k:\n",
    "            res = presum[j] - presum[i]\n",
    "        while j < n:\n",
    "            cnt[nums[j]] += 1\n",
    "            cnt[nums[i]] -= 1\n",
    "            if cnt[nums[i]] == 0:\n",
    "                del cnt[nums[i]]\n",
    "            i += 1\n",
    "            if len(cnt) == k:\n",
    "                res = max(res, presum[j+1] - presum[i])\n",
    "            # print(res)\n",
    "            j += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # 1. 求前缀和\n",
    "        prefix_sum = [0]\n",
    "        for num in nums:\n",
    "            prefix_sum.append(prefix_sum[-1] + num)\n",
    "\n",
    "        # 2. 求最大值 滑动窗口\n",
    "        max_sum = 0\n",
    "        window_count = {}\n",
    "        for i in range(len(nums) - k + 1):\n",
    "\n",
    "            if not window_count:  # 初始化window_count\n",
    "                for j in range(i, i + k):\n",
    "                    window_count[nums[j]] = window_count.get(nums[j], 0) + 1\n",
    "            else:\n",
    "                window_count[nums[i - 1]] -= 1\n",
    "                if window_count[nums[i - 1]] == 0:\n",
    "                    window_count.pop(nums[i - 1])\n",
    "\n",
    "                if nums[i + k - 1] in window_count:\n",
    "                    window_count[nums[i + k - 1]] += 1\n",
    "                else:\n",
    "                    window_count[nums[i + k - 1]] = 1\n",
    "\n",
    "            if len(window_count) == k:\n",
    "                max_sum = max(max_sum, prefix_sum[i + k] - prefix_sum[i])\n",
    "\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        prefix = list(accumulate(nums))\n",
    "        start = res = 0\n",
    "\n",
    "        appear = dict()\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            s = nums[i]\n",
    "\n",
    "            if s in appear and appear[s] >= start:\n",
    "                start = appear[s] + 1\n",
    "            \n",
    "            if i - start + 1 >= k:\n",
    "                res = max(res, prefix[i] - prefix[start-1] if start > 0 else prefix[i])\n",
    "                start += 1\n",
    "            \n",
    "            appear[s] = i\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, mp = [0] * n, {}\n",
    "        for i in range(n):\n",
    "            if nums[i] in mp:\n",
    "                left[i] = mp[nums[i]] + 1\n",
    "            mp[nums[i]] = i\n",
    "\n",
    "        prefix = list(accumulate(nums, initial=0))\n",
    "\n",
    "        ans, i = 0, 0\n",
    "        for j in range(n):\n",
    "            i = max(i, left[j])\n",
    "            if j - i + 1 == k:\n",
    "                ans = max(ans, prefix[j + 1] - prefix[i])\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        s = set()\n",
    "        t = 0\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        cnts = Counter()\n",
    "        for i in range(k):\n",
    "            s.add(nums[i])\n",
    "            cnts[nums[i]] += 1\n",
    "            t += nums[i]\n",
    "        if len(s) == k: ans = t\n",
    "        for l in range(k, n):\n",
    "            cnts[nums[l - k]] -= 1\n",
    "            if cnts[nums[l - k]] == 0:\n",
    "                s.remove(nums[l - k])\n",
    "            s.add(nums[l])\n",
    "            cnts[nums[l]] += 1\n",
    "            t -= nums[l - k]\n",
    "            t += nums[l]\n",
    "            if len(s) == k and t > ans: ans = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumSubarraySum(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        pre = [0] * (n + 1)\r\n",
    "        for i in range(n):\r\n",
    "            pre[i + 1] = pre[i] + nums[i]\r\n",
    "        cnt = Counter(nums[:k-1])\r\n",
    "        res = float('-inf')\r\n",
    "        for i in range(k, n + 1):\r\n",
    "            cnt[nums[i-1]] += 1\r\n",
    "            if len(cnt) == k:\r\n",
    "                res = max(res, pre[i] - pre[i-k])\r\n",
    "            cnt[nums[i-k]] -= 1\r\n",
    "            if cnt[nums[i-k]] == 0:\r\n",
    "                cnt.pop(nums[i-k])\r\n",
    "        return res if res != float('-inf') else 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
